from typing import List

# 方法一：通过二进制枚举子集
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        # 枚举子集，通过二进制方法
        n=len(nums)
        ans=[]
        # 遍历从0 到 2^n-1的所有整数
        for i in range(1<<n):
            subset=[]
            # 通过 二进制 判断
            for j in range(n):
                # 检查第j位是否为1， 比如 001 011，是1的就添加值
                if (i>>j) &1:
                    subset.append(nums[j])
            ans.append(subset)
        return ans

# 方法二：递归
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        path = []
        n = len(nums)
        def dfs(i):
            ans.append(path.copy())
            if i == n:
                return
                # 非边界条件
            for j in range(i, n):
                path.append(nums[j])
                dfs(j + 1)
                path.pop()

        dfs(0)
        return ans
